/*
 * Поиск подстрок
 *
 * Aho-Corasick
 */

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>

/* #define DEBUG */
/* #define MEMDEBUG */

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif
#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))
#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MIN(a, b)	((a) < (b) ? (a) : (b))

/* queue */
struct queue {
	char *data;
	size_t _data_size;

	int head;
	int n;
	int _max;
};

struct ac_node {
	struct ac_node *prefix;
	struct ac_node *out;
	struct ac_node *prev;

	int leaf_count;
	struct st_node *set; /* search tree, used at adding patterns stage */
	struct st_node *leaf; /* sorted array of leaf nodes,
							 populated before starting matching stage and
							 after adding the last pattern */

	bool final_pattern, root;

	int _descendants_count;
};

/* search tree node */
struct st_node {
	char key;
	struct ac_node *ptr;
	struct st_node *left, *right;
};

/* {{{ memory allocation wrappers */
extern char *
s_calloc(size_t n, size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): calloc %lu times %lu bytes (tot %.4f MiB)\n",
			__func__, n, size, ((float) n * size) / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = calloc(n, size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern char *
s_malloc(size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): malloc %lu bytes (%.4f MiB)\n",
			__func__, size, (float) size / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = malloc(size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern char *
s_realloc(char *oldptr, size_t newsize)
{
	void *newptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size of %lu (%.4f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): newptr %p\n", __func__, newptr);
#endif /* MEMDEBUG */
	return newptr;
}
/* }}} */

/* {{{ queue */
extern struct queue *
queue__new(const int n, const size_t elem_size)
{
	struct queue *q = NULL;

	assert(n >= 1); /* WHO DOES THIS ?!? >:( */
	assert(elem_size > 0);

	q = (struct queue *) s_malloc(sizeof *q);
	q->data = (char *) s_calloc(n, elem_size);
	q->_data_size = elem_size;
	q->head = 0;
	q->n = 0;
	q->_max = n;

	return q;
}

extern int
queue__push(struct queue *q, const void *p)
{
	assert(q != NULL);
	assert(p != NULL);

	if (q->n >= q->_max) {
		#ifdef QUEUE_DEBUG
		fprintf(stderr, "%s(): q->n (%d) >= q->_max (%d), can't push any deeper :-(\n",
				__func__, q->n, q->_max);
		#endif /* QUEUE_DEBUG */
		return -1;
	}

	memcpy(q->data + ((q->head + q->n++) % q->_max) * q->_data_size, p, q->_data_size);
	#ifdef QUEUE_BEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif

	return 0;
}

extern int
queue__pop(struct queue *q, void *buf)
{
	assert(q != NULL);
	assert(buf != NULL);

	memcpy(buf, q->data + (q->head) * q->_data_size, q->_data_size);
	q->head = (q->head + 1) % q->_max;
	q->n--;
	#ifdef QUEUE_BEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif

	return 0;
}

extern int
queue__cleanup(struct queue *q)
{
	S_assert(q != NULL);
	if (q == NULL)
		return -1;

	if (q->_max == 0 || q->data == NULL)
		return 1;

	free(q->data);
	q->data = NULL;
	free(q);

	return 0;
}
/* }}} */

/* {{{ simple search-tree-based set */
struct st_node *
set_add(struct st_node *root, char new_key)
{
	struct st_node *prev;

	if (root == NULL)
		return NULL; /* look out for this too */

	while (root) {
		prev = root;
		if (new_key > root->key)
			root = root->right;
		else
			root = root->left;
	}
	if (new_key > prev->key)
		root = prev->right = s_calloc(1UL, sizeof *prev);
	else
		root = prev->left = s_calloc(1UL, sizeof *prev);
	root->key = new_key;
	root->ptr = root->left = root->right = NULL;
	return root;
}

struct st_node *
set_seek(struct st_node *root, char key)
{
	while (root) {
		if (root->key == key)
			return root;
		else if (root->key > key)
			root = root->left;
		else
			root = root->right;
	}

	return NULL; /* ouch! ya gotta look out for that! */
}

void
print_set(struct st_node *st)
{
	if (st->left)
		print_set(st->left);
	fputc(st->key, stderr);
	if (st->right)
		print_set(st->right);
}
/* }}} */

/* {{{ aho-corasick */
int
ac__reg_word(struct ac_node *root, const char *w)
{
	register int i;
	struct st_node *next;

	i = 0;
	while (w[i]) {
		if (root->set == NULL) {
			/* this is a little ugly, but oh well.. */
			root->set = s_calloc(1UL, sizeof *root->set);
			root->set->key = w[i];
			root->set->ptr = s_calloc(1UL, sizeof *root);
			root->set->ptr->prev = root;
			root->leaf_count = 1;
		}

		if (next = set_seek(root->set, w[i]), next == NULL) {
			next = set_add(root->set, w[i]);
			next->ptr = s_calloc(1UL, sizeof *root);
			next->ptr->prev = root;
			root->leaf_count++;
		}
		root = next->ptr;
		i++;
	}
	root->final_pattern = true;

	return 0;
}

static int
ac__count_nodes(struct ac_node *node, struct st_node *link)
{
	int count = 0;

	if (node != NULL && link == NULL) {
		count += 1;
		count += ac__count_nodes(NULL, node->set);
	} else if (node == NULL && link != NULL) {
		count += ac__count_nodes(NULL, link->left);
		count += ac__count_nodes(NULL, link->right);
		count += ac__count_nodes(link->ptr, NULL);
	}
	/* i didnt even know i could do that! */

	return count;
}

inline struct st_node *
far_right(struct st_node *list)
{
	struct st_node *r = list;
	while (r && r->right) r = r->right;
	return r;
}

inline struct st_node *
far_left(struct st_node *list)
{
	struct st_node *l = list;
	while (l && l->left) l = l->left;
	return l;
}

/*
 * Turn search-tree set into a linked list
 */
static struct st_node *
__unnamed(struct st_node *set_root)
{
	struct st_node *list;

	list = __unnamed(set_root->left);

	list = far_right(list);
	list->right = set_root;
	far_right(list)->left = list;
	/* TODO */

	return list;
}

static void
ac__unroll_set(struct ac_node *node, struct st_node *link)
{
	static int index = 0; /* don't remove 'static'! */

	if (node != NULL && link == NULL) {
		S_assert(node->leaf == NULL);
		if (node->leaf_count == 0)
			return; /* apparently, this node really is a leaf,
					   nothing to do, exiting */

		/* This can potentially eat a lot of memory */
		node->leaf = s_calloc(node->leaf_count, sizeof *node->set);

		/* careful here.. */
		ac__unroll_set(node, node->set);
		index = 0;
	} else if (node != NULL && link != NULL) {
		/*
		 * If we somehow call ourself and second argument ends up
		 * being NULL, we're screwed!
		 */
		if (link->left)
			ac__unroll_set(node, link->left);

		node->leaf[index] = *link;
		index += 1;
		debug_fprintf((stderr, "%lx: node->leaf[%d] = \'%c\'\n",
					(long unsigned) &node, index - 1, link->key));

		if (link->right)
			ac__unroll_set(node, link->right);
	}
}

static void
ac__unroll_all_sets(struct ac_node *node)
{
	int i;

	ac__unroll_set(node, NULL);
	for (i = 0; i < node->leaf_count; i++)
		ac__unroll_all_sets(node->leaf[i].ptr);
}

int
ac__prefix_func(struct ac_node *acroot)
{
	struct queue *q;
	struct ac_node *nd, *nxt; /* current node in bfs */
	struct ac_node *pref; /* looks for suitable prefix function value */
	struct st_node *next_link;
	char c;
	register int i;

	ac__unroll_all_sets(acroot);
	q = queue__new(ac__count_nodes(acroot, NULL) - 1, sizeof acroot);
	queue__push(q, &acroot);
	acroot->prefix = acroot;
	S_assert(acroot->prev == acroot);
	acroot->prev = acroot;

	while (q->n) {
		queue__pop(q, &nd);

		for (i = 0; i < nd->leaf_count; i++) {
			nxt = nd->leaf[i].ptr;
			c   = nd->leaf[i].key;
			queue__push(q, &nxt);

			/*
			 * So in a situation like
			 *    p  -[c]-> v
			 * we traverse all p's prefix function values until we find
			 * a p* node that has the same -[c]-> edge. Therefore, we have
			 *    p* -[c]-> v*
			 * and v's prefix function will be the v* node.
			 *
			 * nd := p
			 * nxt := v
			 */
			/*
			 * Prefix function value for trie root and
			 * all its direct descendants is trie root.
			 */
			if (nd->root) {
				nxt->prefix = nxt->prev;
			} else {
				S_assert(nxt->prev == nd);

				pref = nd->prefix;
				while (!(next_link = set_seek(pref->set, c)) &&
						pref->root == false)
					pref = pref->prefix;
				nxt->prefix = next_link ? next_link->ptr : acroot;

				/* The "out" function. */
				if (nxt->prefix->final_pattern)
					nxt->out = nxt->prefix;
				else if (nxt->prefix->out && nxt->prefix->out->final_pattern)
					nxt->out = nxt->prefix->out;
				else {
					S_assert(nxt->out == NULL);
					nxt->out = NULL;
				}
			}
		}
	}

	queue__cleanup(q);
	return 0;
}

int
ac__contains(struct ac_node *ac_dfa, const char *text)
{
	register struct ac_node *state = ac_dfa;
	struct st_node *link;
	int i = 0;
	int ans = 0;

	while (text[i]) {
		while (state != ac_dfa && !set_seek(state->set, text[i]))
			state = state->prefix;

		if (link = set_seek(state->set, text[i]), link != NULL)
			state = link->ptr;

		if (state->final_pattern)
			ans = 1;

		if (state->out) {
			/*
			struct ac_node *out_func_res = state->out;
			while (out_func_res) {
				add_matched_pattern();
				out_func_res = out_func_res->out;
			}
			 */
			ans = 1;
		}
		i++;
	}

	return ans;
}

void
ac__cleanup(struct ac_node *node, struct st_node *link)
{
	if (node && !link) {
		if (node->set) {
			#ifdef DEBUG
			fprintf(stderr, "%lx: node->set ~= <", &node);
			print_set(node->set);
			fprintf(stderr, ">\n");
			#endif /* DEBUG */
			ac__cleanup(NULL, node->set);
		}
		if (node->leaf_count > 0)
			free(node->leaf);
		free(node);
	} else if (!node && link) {
		if (link->left)
			ac__cleanup(NULL, link->left);
		if (link->right)
			ac__cleanup(NULL, link->right);
		ac__cleanup(link->ptr, NULL);
		free(link);
	} else {
		fprintf(stderr, "pardon me?\n");
	}
}
/* }}} */

int
main(int argc, char **argv)
{
	char *word, *lf;
	int n;
	struct ac_node *dfa;

	dfa = s_calloc(1UL, sizeof *dfa);
	dfa->root = true;
	dfa->prev = dfa;
	word = s_malloc(252UL);

	fgets(word, 251, stdin);
	sscanf(word, "%d", &n);
	while (n--) {
		(void) fgets(word, 251, stdin);
		if (lf = strrchr(word, '\n'), lf)
			*lf = '\0';
		ac__reg_word(dfa, word);
	}
	ac__prefix_func(dfa);

	while (fgets(word, 251, stdin)) {
		if (lf = strrchr(word, '\n'), lf)
			*lf = '\0';
		if (ac__contains(dfa, word))
			puts(word);
	}

	ac__cleanup(dfa, NULL);
	free(word);
	return 0;
}
